%------------------------------------------------------------------------
% ------------------------------------------------------------------------
% Trabalho de Conclusão de Curso
% Universidade Federal do Pará
% Instituto de Ciências Exatas e Naturais
% Manoel Afonso Pereira de Lima Filho
% ------------------------------------------------------------------------
% ------------------------------------------------------------------------

\documentclass[
	% -- opções da classe memoir --
	12pt,				% tamanho da fonte
	openright,			% capítulos começam em pág ímpar (insere página vazia caso preciso)
	twoside,			     % para impressão em verso e anverso. Oposto a oneside
	a4paper,			     % tamanho do papel. 
	% -- opções da classe abntex2 --
	%chapter=TITLE,		% títulos de capítulos convertidos em letras maiúsculas
	%section=TITLE,		% títulos de seções convertidos em letras maiúsculas
	%subsection=TITLE,	     % títulos de subseções convertidos em letras maiúsculas
	%subsubsection=TITLE,    % títulos de subsubseções convertidos em letras maiúsculas
	% -- opções do pacote babel --
	english,			     % idioma adicional para hifenização
	brazil,				% o último idioma é o principal do documento
	]{abntex2}
	
% ---
% PACOTES
% ---

% ---
% Pacotes fundamentais 
% ---
\usepackage{cmap}                  % Mapear caracteres especiais no PDF
\usepackage{lmodern}               % Usa a fonte Latin Modern			
\usepackage[T1]{fontenc}           % Selecao de codigos de fonte.
\usepackage[utf8]{inputenc}		% Codificacao do documento (conversão automática dos acentos)
\usepackage{lastpage}			% Usado pela Ficha catalográfica
\usepackage{indentfirst}           % Indenta o primeiro parágrafo de cada seção.
\usepackage{color}				% Controle das cores
\usepackage{amsfonts}              % Fontes matemáticas especiais
\usepackage{graphicx}			% Inclusão de gráficos
\usepackage{epstopdf}			% Inclusão de gráficos vetoriais
\usepackage{pdflscape}             % Rotacionar a página
\usepackage[lined,boxed,linesnumbered,commentsnumbered,portugues]{algorithm2e}
\usepackage{hyperref}
\newsubfloat{figure}               % Allow subfloats in figure environment

% ---
% Pacotes de citações
% ---
\usepackage[hyperpageref]{backref}                % Páginas com as citações na bibl
\usepackage[alf, abnt-etal-list=0]{abntex2cite}   % Citações padrão ABNT

% --- 
% CONFIGURAÇÕES DE PACOTES
% --- 

% ---
% Configurações do pacote backref
% Usado sem a opção hyperpageref de backref
\renewcommand{\backrefpagesname}{Citado na(s) página(s):~}
% Texto padrão antes do número das páginas
\renewcommand{\backref}[1]{}
% Separador de seções
\renewcommand{\backreftwosep}{ e~}
% Define os textos da citação
\renewcommand*{\backrefalt}[4]{
	\ifcase #1 %
		Nenhuma citação no texto.%
	\or
		Citado na página #2.%
	\else
		Citado #1 vezes nas páginas #2.%
	\fi}%
% ---

% --- Configura a capa específica da UFPA
\renewcommand{\imprimircapa}{
\begin{capa}

\center
\includegraphics[scale=0.5]{Imagens/logo_ufpa.jpg}

 { \ABNTEXchapterfont
 UNIVERSIDADE FEDERAL DO PARÁ\\
 INSTITUTO DE CIÊNCIAS EXATAS E NATURAIS\\
 FACULDADE DE COMPUTAÇÃO\\}
   \vspace*{4.0cm}
 
 { \ABNTEXchapterfont\large
   \textbf{\imprimirautor}}
   \vspace*{3.0cm}

 {\ABNTEXchapterfont\LARGE
 \textbf{\imprimirtitulo}}

 \vspace*{\fill}
 {\large\imprimirlocal}
 \par
 {\large\imprimirdata}
 \vspace*{1cm}
\end{capa}
}
% --

% ---
% Configurações de aparência do PDF final
% alterando o aspecto da cor azul
\definecolor{blue}{RGB}{41,5,195}

% informações do PDF
\makeatletter
\hypersetup{
     	%pagebackref=true,
		pdftitle={Implementação de um Cifrador de Bloco Simétrico Baseado em Algoritmo Genético}, 
		pdfauthor={Manoel Afonso Pereira de Lima Filho},
    	     pdfsubject={Trabalho de Conclusão de Curso apresentado à Faculdade de Computação como requisito para a obtenção do título de bacharel em Ciência da Computação, sob orientação do Prof. Dr. Claudomiro de Souza de Sales Junior.},
	     pdfcreator={LaTeX com abnTeX2},
		pdfkeywords={algoritmo genético, entropia, cifrador de bloco}, 
		colorlinks=true,       		% false: boxed links; true: colored links
     	linkcolor=blue,          	% color of internal links
    	     citecolor=blue,        		% color of links to bibliography
    	     filecolor=magenta,      		% color of file links
		urlcolor=blue,
		bookmarksdepth=4
}
\makeatother
% --- 

% --- 
% Espaçamentos entre linhas e parágrafos 
% --- 

% O tamanho do parágrafo é dado por:
\setlength{\parindent}{1.3cm}

% Controle do espaçamento entre um parágrafo e outro:
\setlength{\parskip}{0.2cm}  % tente também \onelineskip


% ================================================================================
% ---
% Informações de dados para CAPA e FOLHA DE ROSTO
% ---
\titulo{Implementação de um Cifrador de Bloco Simétrico Baseado em Algoritmo Genético}
\autor{Manoel Afonso Pereira de Lima Filho}
\local{Belém - PA}
\data{\the\year}
\orientador{Claudomiro de Souza de Sales Junior}
\instituicao{
  Universidade Federal do Pará -- UFPA
  \par
  Instituto de Ciências Exatas e Naturais
  \par
  Faculdade de Computação
  \par
  Bacharelado em Ciência da Computação
}
\tipotrabalho{Trabalho de Conclusão de Curso}
% O preambulo deve conter o tipo do trabalho, o objetivo, 
% o nome da instituição e a área de concentração 
\preambulo{Trabalho de Conclusão de Curso apresentado à Faculdade de Computação como requisito para a obtenção do título de bacharel em Ciência da Computação, sob orientação do Prof. Dr. Claudomiro de Souza de Sales Junior.}
% ---

% ---
% compila o índice
% ---
\makeindex
% ---

% ----
% Início do documento
% ----
\begin{document}

% Retira espaço extra obsoleto entre as frases.
\frenchspacing 

% ----------------------------------------------------------
% ELEMENTOS PRÉ-TEXTUAIS
% ----------------------------------------------------------
% \pretextual

% ---
% Capa
% ---
\imprimircapa
% ---

% ---
% Folha de rosto
% (o * indica que haverá a ficha bibliográfica)
% ---
\imprimirfolhaderosto
% ---

% Isto é um exemplo de Folha de aprovação, elemento obrigatório da NBR
% 14724/2011 (seção 4.2.1.3). Você pode utilizar este modelo até a aprovação
% do trabalho. Após isso, substitua todo o conteúdo deste arquivo por uma
% imagem da página assinada pela banca com o comando abaixo:
%
% \includepdf{folhadeaprovacao_final.pdf}
%
% \begin{folhadeaprovacao}

%   \begin{center}
%     {\ABNTEXchapterfont\large\imprimirautor}

%     \vspace*{\fill}\vspace*{\fill}
%     {\ABNTEXchapterfont\bfseries\Large\imprimirtitulo}
%     \vspace*{\fill}
    
%     \hspace{.45\textwidth}
%     \begin{minipage}{.5\textwidth}
%         \imprimirpreambulo
%     \end{minipage}%
%     \vspace*{\fill}
%    \end{center}
%     %TODO atualizar a data.
%    Trabalho aprovado. \imprimirlocal, 01 de outubro de 2013:

%    \assinatura{\textbf{\imprimirorientador} \\ Orientador} 
%    \assinatura{\textbf{Dionne Cavalcante Monteiro } \\ Membro da Banca}
%    \assinatura{\textbf{Fábio Manoel França Lobato} \\ Membro da Banca}
      
%    \begin{center}
%     \vspace*{0.5cm}
%     {\large\imprimirlocal}
%     \par
%     {\large\imprimirdata}
%     \vspace*{1cm}
%   \end{center}
  
% \end{folhadeaprovacao}
% ---

% ---
% Agradecimentos
% ---
\begin{agradecimentos}
A Deus por permitir-me chegar até aqui.

Ao professor Claudomiro de Souza de Sales Junior pela atenção e dedicação dados na orientação deste trabalho, me motivando a seguir no meio acadêmico, bem como seus ensinamentos que me ajudaram na minha formação profissional.

A toda a minha família, em especial à minha mãe, Lucy Mary G. Costa, pela sua criação dada a mim e por sempre me apoiar e me ajudar durante esses quatro anos de curso.

A todos os meus amigos que também me apoiaram e me ajudaram de inúmeras formas durante esses oito semestres, e em especial a Carlos Gustavo Resque dos Santos, Reginaldo Cordeiro dos Santos Filho e Thiago Sylas Antunes da Costa, pela rica troca de conhecimentos e experiências que contribuíram para a minha vida profissional.

A todas as pessoas citadas os meus mais sinceros agradecimentos por fazerem parte da minha vida.
\end{agradecimentos}


% ---
% RESUMOS
% ---

% --- Português ---
\setlength{\absparsep}{18pt} % ajusta o espaçamento dos parágrafos do resumo

\begin{resumo}
Visto que muitos algoritmos de criptografia baseados em algoritmos genéticos seguem basicamente um mesmo \textit{modus operandi} e carecem de elementos clássicos de um AG, faz-se necessário um estudo de como os vários operadores genéticos impactam na segurança fornecida por tais algoritmos. Com isso, foi desenvolvido um cifrador de bloco com chave simétrica utilizando os principais conceitos de algoritmos genéticos e tendo como destaque a utilização da entropia como a função \textit{fitness}. Constatou-se que o cifrador elaborado possui grande capacidade em criar mensagens cifradas pseudo-randômicas com alto valor de entropia, superando os algoritmos encontrados na literatura.
%Também se verificou como a utilização dos operadores tradicionais de um AG afetam o desempenho global do cifrador.
\vspace{\onelineskip}

\noindent \textbf{Palavras-chaves}: algoritmo genético. criptografia. entropia.
\end{resumo}

% --- Inglês ---
\begin{resumo}[Abstract]
\begin{otherlanguage*}{english}
As many cryptographic algorithms based on genetic algorithm follow basically the same \textit{modus operandi} and lack classical elements of a GA, there is a need for a study of how the many genetic operators impact in the security provided by such algorithms. In that way, a block cipher with simmetrical key has been developed using the main concepts of genetic algorithms and having the use of entropy as fitness function as highlight. It was found that the developed cipher has a large capacity in create cipher pseudo-random messages with high entropy values, overcoming the algorithms found on the literature.
\vspace{\onelineskip}

\noindent \textbf{Keywords}: genetic algorithm, cryptography, entropy.
\end{otherlanguage*}
\end{resumo}


% ---
% inserir lista de ilustrações
% ---
\pdfbookmark[0]{\listfigurename}{lof}
\listoffigures*
\cleardoublepage
% ---

% ---
% inserir lista de tabelas
% ---
\pdfbookmark[0]{\listtablename}{lot}
\listoftables*
\cleardoublepage
% ---

% ---
% inserir lista de abreviaturas e siglas
% ---
 \begin{siglas}
   \item[AG] Algoritmo Genético
   \item[CBC] \textit{Cipher Block Chaining}
   \item[COA] \textit{Ciphertext-only Attack} (Ataque de Cifra Conhecida)   
   \item[DES] \textit{Data Encryption Standard}
   \item[ECB] \textit{Eletronic Codebook}
   \item[ICIGA] \textit{Improved Cryptography Inspired by Genetic Algorithms}
   \item[JPEG] \textit{Joint Photographic Experts Group}
   \item[KPA] \textit{Known Plaintext Attack} (Ataque de Texto Aberto Conhecido)
   \item[NLFSR] \textit{Non-linear Feedback Shift Register}
   \item[PCM] \textit{Pulse-code Modulation}
   \item[WAVE] \textit{Waveform Audio File Format}   
 \end{siglas}
% ---

% ---
% inserir lista de símbolos
% ---
% \begin{simbolos}
%   \item[$ \Gamma $] Letra grega Gama
%   \item[$ \Lambda $] Lambda
%   \item[$ \zeta $] Letra grega minúscula zeta
%   \item[$ \in $] Pertence
% \end{simbolos}
% ---


% ---
% inserir o sumário
% ---
\pdfbookmark[0]{\contentsname}{toc}
\tableofcontents*
\cleardoublepage
% ---

% ----------------------------------------------------------
% ELEMENTOS TEXTUAIS
% ----------------------------------------------------------
\textual

% ----------------------------------------------------------
% Introdução
% ----------------------------------------------------------
\chapter[Introdução]{Introdução}

\section{Contextualização e Objetivos}

A criptografia é um ramo da computação cujo objetivo é tornar a comunicação ininteligível para todos exceto para o(s) destinatário(s) desejados. Ela desenvolve métodos de enviar mensagens de forma manipulada a fim de que apenas os destinatários tenham condições de convertê-la novamente para a forma legível. Existem várias soluções eficientes disponíveis com o objetivo de proteger dados sensíveis para um grande número de aplicações, entre elas, dados pessoais, segurança em rede e comunicações militares.

Atualmente, com uma grande demanda por transmissão de sinal digital, a segurança da informação se tornou crítica e imperativa em aplicações de transmissão multimídia. A fim de proteger informações sensíveis de leitores indesejáveis, reprodução ilegal e modificações, vários algoritmos de criptografia foram desenvolvidos. Existem dois tipos de criptografia: criptografia simétrica e criptografia assimétrica. O modelo simétrico utiliza a mesma chave para criptografar e decriptografar. Já na criptografia assimétrica, são usadas duas chaves, uma para a criptografia, conhecida como chave pública e uma para a cifragem, conhecida como chave privada. Em geral, a criptografia simétrica é utilizada em dados pessoais devido a sua alta performance, enquanto que a assimétrica é utilizada em assinatura digital e distribuição de chaves.

Um sistema criptográfico consiste em um conjunto de algoritmos necessários para se implementar uma forma específica de cifragem e decifragem. Geralmente, eles são constituídos por três algoritmos: um para a geração de chave, um para a cifragem e outro para a decifragem. A chave representa um parâmetro que determina uma transformação nos dados fornecidos ao sistema criptográfico, podendo ser uma transformação de informação legível para ilegível ou vice-versa. A primeira transformação corresponde ao processo de cifragem, e a última, o de decifragem.

\section{Motivação}

O estudo de algoritmos genéticos é interessante pois pode-se encontrar soluções quase-ótimas, porém aceitáveis, utilizando sua heurística. A criptografia é uma área extensa e, portanto, o desenvolvimento de AG's nessa área se torna fundamental para se compreender até onde eles podem ser utilizados.

Dado que muitos trabalhos feitos nessa área apenas utilizam conceitos do algoritmo genético, faz-se necessário elaborar um sistema criptográfico que utilize todos os componentes de um AG. Isso mostrará quais os potenciais de um sistema criptográfico elaborado da maneira proposta, principalmente no que diz respeito ao uso de recursos computacionais e segurança da informação. Além disso, o desenvolvimento de um sistema que utilize criptografia simétrica nessa área pode contribuir para outros trabalhos que desejem implementar outros modos de operação ou sua adaptação para um cifrador de fluxo.

\section{Justificativa}

O trabalho propõe o desenvolvimento de um sistema criptográfico simétrico baseado em algoritmo genético. Diferentemente do que é tipicamente desenvolvido nessa área, o algoritmo genético do sistema será composto por todos os operadores fundamentais (seleção, cruzamento, mutação e \textit{fitness}). O sistema também irá recuperar o arquivo criptografado de modo que o arquivo legível decriptografado seja idêntico ao arquivo original, o que pode ser constatado por um algoritmo de \textit{hash}. Além disso, o domínio dos valores da chave secreta será maior do que os domínios dos algoritmos mostrados anteriormente, dificultando ataques por força bruta.

Portanto, o presente trabalho fornecerá mais uma alternativa de proteção de dados. São analisados aspectos como velocidade de execução, uso de memória, nível de segurança da informação, bem como a que forma que diferentes abordagens dos operadores do AG
interferem no desempenho e segurança criptográfica do sistema.

\section{Metodologia}

O desenvolvimento deste trabalho consiste na análise dos algoritmos genéticos relacionados à criptografia presentes na literatura a fim de propor melhorias na sua arquitetura demonstrando com este trabalho uma aplicação dos operadores genéticos para fins de criptografia. Por conseguinte, são realizados testes para se obter os parâmetros ideais do algoritmo e para constatar que a mensagem cifrada não possua nenhuma relação óbvia com a mensagem original.

\section{Estrutura do trabalho}

Este trabalho está organizado da seguinte forma: o Capítulo 2 aborda a justificativa do trabalho, o Capítulo 3 a motivação, o Capítulo 4 apresenta todos os conceitos de criptografia e algoritmos genéticos utilizados neste trabalho, o Capítulo 5 apresenta e realiza uma análise dos trabalhos da literatura, o Capítulo 6 descreve o funcionamento e a estrutura do cifrador proposto, o Capítulo 7 apresenta e discute os resultados experimentais e o Capítulo 8 mostra as conclusões obtidas e os trabalhos futuros.

% ----------------------------------------------------------
% Referencial Teórico
% ----------------------------------------------------------
\chapter[Referencial Teórico]{Referencial Teórico}

\section{Criptografia}

\subsection{Texto Aberto e Texto Cifrado}

No contexto da criptografia, a mensagem que se deseja enviar para um destinatário é designada \textit{texto aberto}. Ela também é referida como \textit{texto claro} ou \textit{plaintext}. Classicamente, este termo era usado visto que as mensagens consistiam majoritariamente de texto ordinário, isto é, formados apenas por caracteres. Na criptografia moderna, entretanto, ele é aplicado a qualquer mensagem que seja legível, seja para humanos ou para máquinas. Dessa forma, arquivos de texto, áudio, vídeo, imagens, binários, entre outros, são classificados como texto aberto. Nesse contexto, qualquer informação que será criptografada será utilizada como entrada do algoritmo de criptografia, o que, por sua vez, irá gerá a \textit{cifra} em um processo denominado cifragem.

A cifra, também conhecida como \textit{texto cifrado} ou \textit{ciphertext} é o resultado do processo de criptografia e é apenas légivel -- seja por humanos ou máquinas -- caso se tenha posse do algoritmo de criptografia e de seus respectivos parâmetros. O processo de decifragem consiste na transformação da cifra de volta em texto aberto.


\subsection{Criptoanálise}

A criptoanálise é o conjunto de técnicas que visam explorar vulnerabilidades de segurança em sistemas criptográficos a fim de obter informações acerca do texto aberto, ainda que se desconheça a chave criptográfica utilizada para gerá-lo.

O ataque de Força-bruta possui o conceito mais simples: verificar todas as possíveis chaves ou senhas até que se encontre a correta. No pior caso, este ataque percorrerá todo o espaço de busca. Nesse sentido, o poder computacional exigido para se descobrir uma chave cresce exponencialmente com o tamanho da mesma. Na criptografia moderna, todos os algoritmos são desenvolvidos de modo que não sejam suscetíveis a esse tipo de ataque em tempo viável.

No ataque de Cifra Conhecida, conhecido também como \textit{Ciphertext-only Attack} (COA), admite-se que o atacante possui um conjunto de cifras. Ela é adequada para se distinguir mensagem cifrada e ruído aleatório em um canal de comunicação que transmite dados constantemente. Nesse tipo de canal, se evita fornecer ao atacante o conhecimento de quando uma informação está sendo transmitida, ainda que criptografada. Por isso, o canal sempre transmite dados: as mensagens úteis, e ruído aleatório quando não se está transmitindo nada.

O Ataque de Texto Aberto Conhecido, ou \textit{Known Plaintext Attack} (KPA), é aquele em que o atacante possui tanto o texto aberto quanto a cifra. Esses pares podem ser utilizados para descobrir informações acerca do funcionamento interno do algoritmo, dos seus componentes, ou até da chave.

Existem ainda outras técnicas que se baseiam em estudar como as diferenças no texto aberto afetam a cifra. A criptoanálise diferencial, por exemplo, é uma aplicação direta deste conceito, e consiste em analisar as transformações sofridas pelo texto aberto em cada passo da cifragem a fim de encontrar componentes ou situações que apresentam um comportamento previsível, permitindo que se consiga recuperar a chave utilizada. Já a criptoanálise linear, é um ataque estatístico que busca correlações entre o texto aberto, a cifra e a chave. Para isso, deve-se encontrar uma equação binária -- sequência de operações XOR -- que mostre alguma tendência entre os objetos de estudo. Feito isso, todos os valores de chaves são testados na equação obtida, até encontrar a chave que maximiza a tendência expressa pela equação.


\subsection{Cifrador}

Um cifrador consiste em um algoritmo que realiza as etapas de cifragem e decifragem. Os cifradores clássicos englobam os cifradores substituição e os de transposição. Os de substituição operam realizando a troca dos símbolos presentes no texto aberto por outros, enquanto que os de transposição realizam um rearranjo nas posições dos símbolos. Tais abordagens não são criptograficamente seguras, visto que podem ser facilmente quebradas por técnicas de criptoanálise. Atualmente, se utiliza os cifradores de produto, que são uma combinação dos cifradores clássicos, utilizando tanto a substituição como a permutação. Uma característica importante de um cifrador é que este utiliza funções bijetivas, ou reversíveis, para a cifragem, o que permite que o algotimo consiga recuperar o texto aberto a partir da cifra.

\subsubsection{Cifrador de Bloco}

Um cifrador de bloco consiste em um algoritmo de criptografia que opera sobre blocos de tamanho fixo do texto aberto. O tamanho do bloco é medido em bits e geralmente são utilizados blocos de 64 bits ou mais. Cada bloco sofre a mesma transformação especificada pelo cifrador de modo que um bloco de texto aberto de \texttt{n} bits resulte em um bloco de texto cifrado de \texttt{n} bits. Isso permite que existam $2^{n}$ blocos de texto aberto possíveis para um dado bloco cifrado. Vale ressaltar que o cifrador de bloco só fornece uma transformação criptograficamente segura em apenas um bloco, e, portanto, se faz necessário utilizar modos de operação para que essa segurança seja estendida para todos os outros blocos.

Outra característica desejável em cifrador de bloco é o Efeito Avalanche. Essa propriedade implica que a mudança de um bit na chave ou da entrada deve resultar na mudança de pelo menos metade dos bits de saída. Caso pequenas mudanças nas entradas não causem uma drástica mudança na cifra, então o cifrador não possui um efeito avalanche forte, o que implica que ele possui uma randomização fraca. Isso permite a um atacante estabelecer padrões nas cifras e encontrar dados das mensagens originais, seja de maneira parcial ou completa. O algoritmo DES (\textit{Data Encryption Standard}), por exemplo, possui um efeito avalanche forte, embora, atualmente já seja considerado inseguro devido ao tamanho reduzido da chave utilizada -- 56 bits.

\subsubsection{\textit{Padding}}

Visto que um cifrador de bloco opera sobre blocos de tamanho fixo, é possível que o tamanho total do texto aberto não seja múltiplo do tamanho do bloco, o que faz com que o último bloco não seja completamente preenchido. Nesse contexto, para que este bloco seja preenhchido e usável pelo cifrador, se utiliza um esquema de \textit{padding}.

O \textit{Bit Padding}, por exemplo, pode ser aplicado em mensagens de tamanho arbitrário, e consiste em adicionar o bit \texttt{1} seguido quantos bits \texttt{0} forem necessários até completar o bloco. Assim, em um conjunto de 10 bits que precisa ser extendido para caber em um bloco de 16 bits terá a seguinte configuração:

| \texttt{\textbf{1011 1010 00}10 0000} | %10 bits com padding de 6

Outro exemplo é o esquema de \textit{padding} ANSI X.923 o qual consiste em incluir valores \texttt{0} mais o número de bytes de padding na última posição, como no exemplo abaixo, no qual foram inseridos 5 bytes de padding:

| \texttt{\textbf{FF FF FF} 0 0 0 0 05} | %3 bytes com padding de 5 em hexadecimal


\subsubsection{Modos de Operação de um Cifrador de Bloco}

Um modo de operação é um algoritmo que especifica como um cifrador de bloco deve ser utilizado repetidamente para poder realizar uma transformação criptograficamente segura em todos os blocos do texto aberto. O uso de um cifrador de bloco em conjunto com um mode de operação é de extrema importância no processo de cifragem, visto que dessa forma é possível ocultar na cifra os padrões presentes no texto aberto.

A maioria dos modos de operação requerem um componente denominado \textit{vetor de inicialização}, ou \texttt{IV}, que permite dar início ao processo de criptografia ou decriptografia. Em geral, é exigido que o \texttt{IV} seja aleatório, ou pseudoaleatório, e único.

O modo de operação mais simples, e inseguro, é o \textit{Eletronic Codebook} (ECB). Nele, cada bloco de texto aberto é cifrado de forma independente dos outros. Dessa maneira, é possível que os padrões presentes no texto aberto sejam visíveis na cifra, o que a torna insegura, especialmente quando se criptografa textos comuns com muitas repetições ou dados gráficos, o que torna este modo operação desaconselhável para qualquer uso criptográfico. 

% Diagrama da cifragem com ECB
\begin{figure}
  \centering
    \includegraphics{Imagens/ecb_encryption}
\caption{Cifragem utilizando ECB, adaptado de \citeauthoronline{wolf_ecb}, 2013.}
\label{fig:ecb_mode}
\end{figure}

O modo \textit{Cipher Chaining Block} (CBC) opera encadeando os resultados de cada cifragem, o que faz com que um bloco da cifra gerado seja dependente de todos os blocos que foram processados antes dele. Isso permite que qualquer mudança feita em um dado bloco da cifra afete o resultado dos blocos posteriores a ele. Assim, é necessário um vetor de inicialização para dar início ao processo e tornar cada mensagem única, o qual precisa ser de conhecimento tanto do emissor quanto do receptor. O diagrama da \autoref{fig:cbc_mode} apresenta como o bloco de texto cifrado é combinado com o bloco anterior.

% Diagrama da cifragem com CBC
\begin{figure}
  \centering
    \includegraphics{Imagens/cbc_encryption}
\caption{Cifragem utilizando CBC, adaptado de \citeauthoronline{wolf_cbc}, 2013.}
\label{fig:cbc_mode}
\end{figure}


\subsubsection{Cifrador de Fluxo}
Os cifradores de fluxo, ou de \textit{stream}, realizam a criptografia usando um byte do texto aberto por vez. Fazem uso de uma chave de fluxo, que é gerada pseudoaleatoriamente, o que permite ocultar as propriedades estatísticas -- os padrões -- da mensagem. Cada byte da chave é combinado com o byte atual do texto aberto por meio da operação \texttt{XOR} (OU-exclusivo).

Este tipo de cifrador é comumente usado em situações onde o tamanho do texto aberto é indefinido, tal qual como os dados de uma rede Wifi, ou outra fonte constante de dados. Entretanto, cuidado deve ser tomado em não se reutilizar a chave, pois abre vulnerabilidades para ataques de criptoanálise, e que por fim podem recuperar as mensagens.


\subsection{Chave}

Para que um cifrador produza um resultado útil, deve-se fornecer a ele, além do texto aberto, os parâmetros que irão definir a saída. Esses parâmetros constituem a chave. Assim, dado um texto aberto \texttt{M}, uma chave \texttt{K}, e uma função de cifragem \texttt{F}, se obtém uma cifra \texttt{C}. Pode-se representar essa transformação por:

$F_{K}(M) = C$

Caso o cifrador utilize criptografia simétrica, então a mesma chave deverá ser utilizada sobre a cifra a fim de recuperar o texto aberto. Assim, para representar o processo de decriptografia, usa-se:

$F_{K}(C) = M$

Uma característica importante é o tamanho da chave, também conhecido como \textit{key size} ou \textit{key length}, sendo medido em bits. Comumente são utilizados valores em pontências de 2. O algoritmo AES (\textit{Advanced Encryption Standard}), por exemplo, suporta chaves com 128, 192 e 256 bits.

A maioria dos algoritmos simétricos são desenvolvidos para que a segurança criptográfica resida na chave, visto que o algoritmo em si será de conhecimento público. Esta noção é embasada no Princípio de Kerckhoffs, que exige que um criptosistema deva ser seguro ainda que se conheça tudo sobre ele, exceto a chave. Dessa forma, a maioria dos projetistas já admitem que um atacante irá imediatamente tomar conhecimento do algoritmo bem como se familiarizar com ele facilmente.

O tamanho da chave deve ser suficientemente grande para evitar um ataque de força bruta, elevando o nível de segurança do algoritmo. Um algoritmo \textit{incondicionalmente seguro} é aquele que, independentemente dos recursos e tempo disponíveis pelo atacante, se mostra inquebrável. Entretanto, para se atingir isso é necessário que o tamanho da chave seja, no mínimo, igual ao tamanho da mensagem e ser usada uma única vez. O algoritmo que atende a esses requisitos é denominado One-time Pad. Porém, ainda que o algoritmo seja de fácil implementação, se terá uma enorme dificuldade no gerenciamento de chaves tão grandes, já que cifradores de bloco podem cifrar mensagens de tamanho arbitrário.

Nesse contexto, os projetistas focam em desenvolver algoritmos que sejam \textit{computacionalmente seguros}, nos quais o tempo e recurso computacional necessários para quebrar um cifrador sejam inviáveis.


\subsection{Confusão e Difusão}

Confusão e difusão são duas propriedades desejáveis em um cifrador para que este tenha um nível de segurança elevado. A confusão visa dificultar o relacionamento entre a cifra e a chave, e é obtida por meio de operações de transposição. Já a difusão consiste em dificultar o relacionamento entre o texto aberto e a cifra, e é obtida por meio de operações de substituição. Ambas visam reduzir ao máximo -- ou, se possível, eliminar -- todos as propriedades estatísticas do texto aberto, como a frequência das letras do alfabeto em um dado idioma. \citeauthoronline{shannon49}, mostra como a difusão contribui em ocultar tais padrões:

\begin{citacao}
No método de difusão, a estrutura estatística de \texttt{M} é "dissipada" em estatísticas de longo alcance -- isto é, em uma estrutura estatística envolvendo longa combinações de letras no criptograma. O efeito aqui é que o inimigo deve interceptar uma quantidade tremenda de material para desvendar esta estrutura, visto que ela é evidente apenas em blocos de probabilidade individual muito pequena. \cite{shannon49}
\end{citacao}


\subsection{Criptografia Simétrica e Criptografia Assimétrica}

A criptografia simétrica, ou criptografia de chave privada, consiste em um conjunto de algoritmos que realizam o processo de cifragem e decifragem utilizando a mesma chave. A característica fundamental dessa abordagem é que a chave deve ser compartilhada previamente entre todas as partes interessadas, sendo esta, a principal desvantagem de sua utilização. Entretanto, a criptografia de chave privada é a mais veloz e a mais recomendada para a criptografia de dados de tamanho arbitrário. A troca de chaves entre as partes interessadas pode ser feita por meio da criptografia assimétrica.

A classe de algoritmos que utilizam duas chaves para os processos de cifragem e decifragem constituem a criptografia assimétrica, ou criptografia de chave pública. Uma das chaves é secreta -- conhecida apenas pelo seu dono, e a outra é pública -- qualquer indivíduo pode obtê-la. Dessa forma, a chave pública é utilizada para cifrar dados enquanto que a privada, para decifrar. Embora as chaves sejam correlacionadas, o custo computacional para se calcular o par de uma dada chave é extremamente grande. Além disso, essa abordagem impõe limites para o tamanho da mensagem, utiliza chaves maiores que a criptografia simétrica, e é notoriamente mais lenta que a mesma, o que justifica o seu uso principalmente na troca de chaves simétricas, fornecimento de autenticidade e sigilo.


\subsection{Entropia}

A entropia é um conceito desenvolvido por \citeauthoronline{shannon49} no campo da Teoria da Informação que mede a quantidade de informação em uma mensagem. Dessa forma, a entropia de uma mensagem é o número de bits de informação na mensagem, ou seja, o número de bits necessários para a menor codificação possível da mensagem. Em resumo, pode-se dizer que ela mede o grau de desordem e imprevisibilidade de uma mensagem. A entropia de uma variável aleatória pode ser calcula pela \autoref{eq:entropia}.

\begin{equation} \label{eq:entropia}
H(X) = - \displaystyle\sum_{x}^{} P(x) log _{p} [P(x)]
\end{equation}

Onde $P(x)$ é a probabilidade de ocorrência de $x$ na mensagem. Vale notar que $P(x) log _{p} [P(x)]$ será 0 se $P(x) = 0$. Comumente se utiliza $p = 2$, o que resulta na entropia medida em bits, porém, outros valores comuns de $p$ são o número de Euler $e$ e 10. A escolha de $p$ é importante pois especifica a quantidade total de todos os valores possíveis de $X$. Assim, um bit, que sempre assume dois valores possíveis, usará $p = 2$; um byte que é composto por 8 bits, e, portanto, 256 valores possíveis, usará $p = 256$, e assim por diante.

Em termos práticos, pode-se considerar o exemplo do lançamento de uma moeda não enviesada. Como a probabilidade do resultado ser cara ou coroa é sempre $1/2$, se tem uma situação de incerteza máxima já que não se tem meios de se prever qual será o resultado na próxima jogada. Dessa forma, o resultado de uma jogada da moeda possui 1 bit de entropia. Alterando a moeda de modo que o resultado seja tendencioso para um dos resultados, o valor da entropia é reduzido, pois se pode prever com um certo grau de certeza qual das faces cairá no próximo lançamento. Agora, utilizando o caso mais extremo -- uma moeda com duas caras ou duas coroas -- a entropia tem valor 0, visto que não há incerteza no resultado.


\section{Algoritmo Genético}

Algoritmos genéticos (AG) são uma parte da área de computação evolucionária, a qual pertence à área de inteligência artificial. São algoritmos inspirados na teoria da evolução de Darwin de modo que a solução desejada é modificada a partir de soluções iniciais. Nesse contexto, um algoritmo genético é uma heurística de busca que visa encontrar soluções ótimas ou quase-ótimas. Há casos em que não se necessita encontrar a solução ótima global, sendo possível usar uma solução quase-ótima que atenda os requisitos do problema. Logo, algoritmos genéticos são adequados para contextos de otimização onde a solução ótima é desconhecida, o espaço de busca é grande ou se deseja uma solução quase-ótima que satisfaça certos critérios. Algoritmos genéticos possuem aplicações em diversas áreas como engenharia, economia, química, matemática e ciência da computação.

O funcionamento básico de um AG consiste em criar um conjunto de possíveis soluções e aplicar nelas os operadores genéticos, de modo que tais soluções se modifiquem -- ou evoluam -- para a solução desejada. Cada solução é denominada indivíduo -- ou fenótipo -- e suas características estão representadas em seu cromossomo. Os cromossomos, da mesma maneira que na Biologia, se subdividem em unidades menores chamadas genes. Cada gene possui uma informação atômica relativa ao indivíduo, cuja codificação depende do problema em questão. No codificação binária, os genes possuem valores binários, enquanto que na inteira possuem valores inteiros e, por fim, na codificação de ponto flutuante -- ou real -- se tem valores fracionários. Assim, o conjunto de todos os genes formam um cromossomo representando um indivíduo, e o conjunto de todos os indivíduos forma a população.

De forma semelhante ao que ocorre na natureza, os indivíduos passam pelo processo de cruzamento gerando descendentes, análogo ao processo de reprodução. Além disso, alguns indivíduos, ocasionalmente, terão os valores de seus genes levemente alterados no processo de mutação, imitando o seu análogo da natureza, visto que a mutação biológica ocorre raramente sobre os indivíduos. A \autoref{fig:fluxograma_ag} apresenta um fluxograma com o funcionamento geral de um algoritmo genético.

% Fluxograma do algoritmo genético
\begin{figure}
  \centering
    \includegraphics[scale=0.5]{Imagens/esquema_geral_AE}
\caption{Fluxograma de um algoritmo genético.}
\label{fig:fluxograma_ag}
\end{figure}

Baseado na teoria da evolução, os indivíduos com melhor aptidão -- ou \textit{fitness} -- serão aqueles com mais chances de serem escolhidos como a solução final. Além disso, tem-se o conceito de geração, isto é, uma período de execução na qual os indivíduos podem se recombinar, para a troca de informações, e sofrer mutação, resultando em mais indivíduos, os quais podem substituir aqueles menos aptos da população atual e, assim, iniciar uma nova geração.

Um atributo importante da população é a diversidade, que pode ser definida \textit{a priori} como a quantidade de soluções distintas presentes nela. Ela está intimamente ligada ao sucesso do algoritmo genético, pois quanto mais informações presentes na população, maior a probabilidade de que a solução desejada seja encontrada por meio dos operadores de cruzamento e mutação. Caso, durante a execução das gerações, o diversidade da população decresça, se corre o risco de o algoritmo resultar em convergência prematura. Esse conceito indica que o algoritmo genético não foi capaz de encontrar a solução ótima global pois ficou estagnado em uma solução ótima local, já que os descendentes gerados não possuem valores de \textit{fitness} superiores aos de seus pais, isto é, não ocorre evolução. Dessa forma, a diversidade genética deve ser mantida sempre em valores altos a fim de evitar resultados ótimos locais. No entanto, a medida da diversidade deve ser feita de acordo com os detalhes de cada problema, visto que não existe uma única forma de medi-la. \citeauthoronline{eiben03}, mostram quais a principais métricas utilizadas:

\begin{citacao}
A \textbf{diversidade} de uma população é uma medida do número de \textit{diferentes} soluções presentes. Não existe uma única medida de diversidade. Tipicamente, se pode referir ao número de diferentes de valores de \textit{fitness} presentes, o número de diferentes fenótipos presentes, ou o número de diferentes genótipos. Outras medidas estatísticas como entropia podem ser usadas. \cite[p. ~20, Tradução nossa]{eiben03}
\end{citacao}

\subsection{Função \textit{Fitness}}

A função \textit{fitness} é uma medida de avaliação de um indivíduo a fim de determinar o quanto ele está próximo da solução desejada, sendo usado, portanto, para escolher qual indivíduo será a melhor solução encontrada. Tipicamente, os indivíduos da população inicial possuem um valor baixo de \textit{fitness}, o qual tende a aumentar conforme a aplicação dos operadores de cruzamento e mutação. Assim, a função \textit{fitness} é o principal elemento do algoritmo que o permite procurar pelas melhores soluções.

\subsection{Inicialização}

O processo de inicialização do algoritmo genético consiste na criação dos indivíduos que formarão a população inicial. Geralmente, são gerados de forma aleatória e a quantidade gerada varia de problema para problema.

\subsection{Seleção}

O operador de seleção consiste em escolher quais indivíduos de uma população passarão pelos operadores de cruzamento e mutação. Indivíduos com maior valor de \textit{fitness} têm maior probabilidade de serem selecionados, o que aumenta a taxa de convergência do AG para a solução ótima global.

\subsubsection{Seleção por Roleta}

A seleção por roleta consiste em associar o \textit{fitness} de cada indivíduo a uma probabilidade de escolha de acordo com a proporção desse \textit{fitness} no somatório de todos os \textit{fitness} da população. Assim, sendo $f_{i}$ o valor do \textit{fitness} de um indivíduo $i$, a probabilidade $p_{i}$ de que ele seja selecionado é dada pela \autoref{eq:selecao_roleta}.

\begin{eqnarray}
F & = & \displaystyle\sum_{j=1}^{N} f_{i} \nonumber \\
p_{i} & = & \frac{f_{i}}{F}
\label{eq:selecao_roleta}
\end{eqnarray}
\noindent onde $N$ é a quantidade total de indivíduos da população e $F$ a soma de todos os valores de \textit{fitness}.

Assim, $p_{i}$ pode ser visto como uma região da roleta alocada  para o indivíduo $i$, de modo que, quanto maior o \textit{fitness}, maiores são as chances de $i$ ser selecionado, como ilustra a \autoref{fig:selecao_roleta}.

% Exemplo da seleção por roleta.
\begin{figure}[h]
  \centering
    \includegraphics[scale=0.7]{Imagens/selecao_roleta}
\caption{Exemplo de distribuição proporcional dos valores de \textit{fitness}.}
\label{fig:selecao_roleta}
\end{figure}

Após o cálculo da proporção do \textit{fitness} de cada indivíduo, sorteia-se um número aleatório $r$ tal que $r \in [0, F)$. O indivíduo cujo $p_{i}$ acumulado -- soma dos $p_{i}$ anteriores -- for maior que $r$, é selecionado. Esse procedimento é realizado até que a quantidade de indivíduos desejados sejam selecionados. A exemplo da \autoref{fig:selecao_roleta}, se $r = 0,45$, e girando a roleta no sentido anti-horário, o indivíduo $B$ será selecionado pois seu $p_{i}$ acumulado é igual a $0,56$.

\subsubsection{Seleção por Ordenamento}

A seleção por ordenamento é similar a seleção por roleta, porém a probabilidade de seleção é proporcional ao \textit{fitness} relativo de cada indivíduo e não ao seu valor absoluto. Isso permite que as diferenças absolutas nos valores dos \textit{fitness} não sejam levadas em consideração.

\begin{citacao}
Esse descarte de informações acerca do \textit{fitness} absoluto pode ter vantagens (usar o \textit{fitness} absoluto pode levar a problemas de convergência) e desvantagens (em alguns casos pode ser importante saber que indivíduo tem um \textit{fitness} bem maior que seu competidor mais próximo). \cite[p.~127, Tradução nossa]{mitchell99}
\end{citacao}
%This discarding of absolute fitness information can have advantages (using absolute fitness can lead to convergence problems) and disadvantages (in some cases it might be important to know that one individual is far fitter than its nearest competitor). Ranking avoids giving the far largest share of offspring to a small group of highly fit individuals, and thus reduces the selection pressure when the fitness variance is high. (p. 127)

Essa seleção consiste em arranjar os indivíduos da população em ordem crescente de \textit{fitness} de 0 a $N$, de modo que, o valor esperado de seleção de cada indivíduo depende de sua posição e não do seu \textit{fitness}. Feito isso, é sorteado um número $x \in [0, N]$. O indivíduo que estiver na posição $x$ é selecionado. Esse procedimento é repetido até que a quantidade de indivíduos desejada seja selecionada. Dessa forma, o ordenamento evita fornecer as maiores chances de seleção para os indivíduos que possuem os maiores \textit{fitness} -- como ocorre na seleção por roleta, reduzindo a pressão de seleção quando a variância dos \textit{fitness} for alta.

\subsubsection{Seleção por Torneio}

A seleção por torneio consiste em escolher os indivíduos por meio de rodadas, nas quais, uma pequena quantidade $k$ de indivíduos da população são escolhidos aleatoriamente e aquele que possuir o maior \textit{fitness} é selecionado. Esse procedimento é repetido até se obter a quantidade desejada para os operadores de cruzamento e mutação. Assim, aumentando-se $k$, indivíduos com menor \textit{fitness} terão menos chances de serem selecionados. Essa característica permite alterar a pressão de seleção facilmente, isto é, permitir se indivíduos com os melhores \textit{fitness} sejam selecionados frequentemente -- diminuindo o valor de $k$ -- ou permitir uma variabilidade maior de fitness -- aumentando o valor de $k$. \textquotedblleft A seleção por torneio é similar com a seleção de ordenamento em termos de pressão de seleção, mas é computacionalmente mais eficiente e mais amena para implementações paralelas\textquotedblright. \cite[p.~127, Tradução nossa]{mitchell99}
%Tournament selection is similar to rank selection in terms of selection pressure, but it is computationally more efficient and more amenable to parallel implementation. (p.127)


\subsection{Cruzamento}

O operador de cruzamento -- ou recombinação -- é o responsável pela troca de informações entre os indivíduos e aumento da diversidade de dados na população, sendo análoga ao processo de reprodução biológica. Consiste em gerar uma solução filha baseada nas informações das soluções pais.

\subsubsection{Cruzamento de um ponto}
%TODO operadores binários
É a forma mais simples de cruzamento \cite[p.~128]{mitchell99}. Um ponto de cruzamento é selecionado aleatoriamente e os dados presentes a partir desse ponto são trocados entre os pais, conforme a \autoref{fig:cruzamento_um_ponto}.

% Cruzamento de um ponto
\begin{figure}
  \centering
    \includegraphics[scale=0.3]{Imagens/crossover_um_ponto}
\caption{Cruzamento de um ponto.}
\label{fig:cruzamento_um_ponto}
\end{figure}

Nota-se que esse tipo de cruzamento sempre irá trocar os dados presentes no fim do cromossomo de cada indivíduo, consequentemente, diminuindo as chances de informações presentes no início de participem do cruzamento.

\subsubsection{Cruzamento de dois pontos}

Consiste em escolher aleatoriamente dois pontos de cruzamento de forma que, os dados presentes na região delimitada pelos pontos sejam trocadas entre os pais. Esse método é capaz de trocar uma variedade maior de regiões entre os pais, ao contrário do cruzamento de um ponto. A \autoref{fig:cruzamento_dois_pontos} ilustra o cruzamento de dois pontos.

% Cruzamento de dois pontos
\begin{figure}
  \centering
    \includegraphics[scale=0.3]{Imagens/crossover_dois_pontos}
\caption{Cruzamento de dois pontos.}
\label{fig:cruzamento_dois_pontos}
\end{figure}

\subsection{Mutação}

O operador de mutação é análogo à mutação biológica. Normalmente, poucos indivíduos do algoritmo terão alguns de seus genes mutados ou alterados, como uma forma de imitar a mutação observada na natureza. A alteração é aplicada somente a alguns genes do indivíduo de modo que as informações que ele guarda não sejam alteradas drasticamente, tal como pode ocorrer no cruzamento.

\begin{citacao}
A mutação é segundo meio pelo qual o AG explora o espaço de busca. Ela pode introduzir características que não estavam presentes na população original e evitar que AG converja rápido demais antes de explorar todo o espaço de busca. \cite[p.~43, Tradução nossa]{randy04}
\end{citacao}
%Mutation is the second way a GA explores a cost surface. It can introduce traits not in the original population and keeps the GA from converging too fast before sampling the entire cost surface

Em cromossomos com representação binária, a mutação consiste apenas em inverter os valores dos genes escolhidos aleatoriamente, 0 para 1 e vice-versa. Para cromossomos com representações inteiras ou de ponto flutuante existem as mutações uniforme e gaussiana.

A mutação uniforme consiste em alterar o valor do gene de acordo com uma variável aleatória $x \in [a, b]$, onde $a$ e $b$ são os limites inferior e superior, respectivamente, da distribuição uniforme. A mutação gaussiana, de maneira similar, utiliza o valor de $x$ seguindo uma distribuição gaussiana.

% ----------------------------------------------------------
% Trabalhos Correlatos
% ----------------------------------------------------------
\chapter[Trabalhos Correlatos]{Trabalhos Correlatos}

Existem vários métodos de criptografia na literatura, dentre eles, uma técnica que vem se destacando é a utilização de algoritmos genéticos nos processos criptográficos. Muitos deles são especializados em processar tipos específicos de arquivos, a exemplo de imagens digitais. As técnicas utilizadas incorporam alguns conceitos de criptografia, como chaves criptográficas e geradores de números pseudoaleatórios. Entretanto, carecem de uma estrutura que represente completamente um algoritmo genético, como a presença de função \textit{fitness} ou um critério de seleção. A seguir, serão exibidos os principais trabalhos correlatos.

% Improved Cryptography Inspired by Genetic Algorithms
\citeonline{tragha06} propõem um cifrador de bloco simétrico denominado ICIGA (\textit{Improved Cryptography Inspired by Genetic Algorithms}) destinado a arquivos de qualquer espécie. O ICIGA é um melhoramento de um cifrador chamado GIC (\textit{Genetic Inspired Cryptography}), dos mesmos autores.

A chave criptográfica do ICIGA é gerada durante o processo de cifragem, denominado sessão. Com isso, a cada execução do algoritmo, chaves distintas são produzidas ainda que o mesmo texto aberto seja fornecido como entrada, diferentemente de cifradores bem conhecidos e fortes, nos quais a chave deve ser fornecida pelo usuário. Nesse contexto, o ICIGA possui um certo grau de não-linearidade em sua operação, dificultando, portanto, algumas técnicas de criptoanálise sobre a chave.

A chave é composta por conjuntos de quadruplas do tipo \textit{(i, j, p, q)}, sendo que o tamanho da chave é determinado pela quantidade de operações aplicadas sobre o texto aberto, a qual pode ser definida pelo usuário. Essa característica permite que o ICIGA seja resistente à técnicas de força-bruta para o descobrimento da chave \cite[p. 6]{tragha06}.

O operador de cruzamento utilizado no algoritmo é baseado no cruzamento de dois pontos. Dado dois blocos de tamanho \texttt{t} bits e dois parâmetros \texttt{p} e \texttt{q}, com $1 \leq p \leq q \leq t$, permuta-se as posições entre \texttt{p} e \texttt{q} na ordem inversa, gerando dois descendentes.

O operador de mutação requer um bloco e dois parâmetros \texttt{p} e \texttt{q}. Executa-se a negação lógica de todos os valores presentes no intervalo de \texttt{p} e \texttt{q}.

As operações definidas acima são aplicadas em cada bloco e após cada operação é realizado um deslocamento à esquerda. Ao fim das \texttt{n} operações aplicadas no bloco é feito um último deslocamento a esquerda para mascarar a distribuição dos blocos. O processo de decifragem consiste na aplicação inversa dos operadores genéticos e deslocamento à direita.

Como pode-se perceber, o ICIGA baseia-se nos principais operadores genéticos e deslocamento de bits para realizar a cifragem. Ele é equivalente a um cifrador de produto com chave de tamanho variável. Embora não seja um algoritmo genético propriamente dito, visto a ausência de critério de seleção, indivíduos e função \textit{fitness}, o ICIGA mostra como um certo nível de segurança pode ser obtido por meio de operações relativamente simples quando comparado a outros cifradores fortes como o Triple-DES e AES \cite[p. 6]{tragha06}.

% Secret Key Encryption Algorithm Using Genetic Algorithm
\citeonline{agarwal12} propôs um cifrador de bloco simétrico destinado à cifragem de imagens que inclui os operadores de cruzamento e mutação para o embaralhamento dos dados no trabalho \textit{Secret Key Encryption Algorithm Using Genetic Algorithm}. A chave secreta é de 192 bits e é composta por três parâmetros: \texttt{a}, \texttt{b} e \texttt{k}. Nessa abordagem, cada bloco -- de tamanho fixo de 64 bits -- representa um indivíduo do algoritmo genético.

O cruzamento e a mutação são aplicados um bloco de cada vez. O operador de cruzamento utilizado é o de dois pontos, os quais são indicados pelos parâmetros \texttt{a} e \texttt{b} da chave, que especificam as posições cujos valores serão trocados. A mutação consiste em calcular o complementar do byte na posição \texttt{k}.

Dado que a chave utilizada possui apenas três parâmetros, cada um sendo um valor inteiro entre 0 e 7, são possíveis $8^{3}$ valores possíveis para a chave. Dessa forma, percebe-se que ela pode ser descoberta por força-bruta sem muito poder computacional, o que compromete a segurança do cifrador. Além disso, não é considerado o \textit{padding}, mesmo que haja necessidade, pois é possível que o último bloco pode não ser preenchido. Dessa forma, caso um texto aberto necessite de \textit{padding} o texto decifrado apresentará bytes a mais do que o original, o que não é desejável, pois se poderá concluir que a mensagem em questão foi alterada. Isso pode ser exemplificado tendo o valor \textit{hash} do texto aberto e do texto decifrado diferentes. Além disso, não há um fator de aleatoriedade no algoritmo, o que o torna bastante previsível e suscetível a ataques de criptoanálise linear.

% A New Approach for Data Encryption Using Genetic Algorithms
Em \textit{A New Approach for Data Encryption Using Genetic Algorithms}, \citeonline{almarimi08} propôs um cifrador de fluxo simétrico destinado a imagens inspirado em conceitos de algoritmos genéticos para aplicações de transmissão de dados em tempo real. O cifrador utiliza um gerador de números pseudo-aleatórios conhecido como \textit{Non-linear Feedback Shift Register} (NLFFSR) para prover uma sequência de números binários com um alto nível de aleatoriedade.

O tipo de cruzamento utilizado é o cruzamento de um ponto e esse atua sobre dois blocos de 8 bits de texto aberto. É, então, sorteada uma posição -- ponto de corte -- para a troca de dados entre os blocos. Feito isso, são aplicadas algumas operações binárias nos descendentes resultantes tendo como base dois valores aleatórios ($Z_{1}$ e $Z_{2}$) produzidos pelo NLFFSR, para que no fim, os bits modificados sejam armazenados como a imagem criptografada. O valores de $Z_{1}$ e $Z_{2}$ são utilizados como a chave secreta para a decifragem, a qual consiste nas mesmas operações binárias e no cruzamento, porém na ordem inversa. 

A técnica tem como ponto forte a aleatoriedade do NLFFSR e as operações binárias, resultando em $M^{\frac{N}{2}}$ resultados possíveis, com \textit{N} sendo o total de bytes da imagem e \textit{M} o tamanho de um indivíduo. Assim, para uma imagem com 256 x 256 de dimensões e \textit{M} igual a 8 \textit{bytes}, tem-se $8^{32768}$ possibilidades de arquivos criptografados. Por se tratar de um cifrador de fluxo, as informações mais sensíveis a serem protegidas são o valor inicial, a função de \textit{feedback} e a função não-linear fornecidas ao NLFFSR para que este gere a sequência pseudo-aleatória. Nesse contexto, a cifrador proposto depende tão somente da sequência fornecida por esse gerador, de tal modo que as operações baseadas em algoritmo genético não acrescentam muito valor criptográfico.

% Bit-Level Encryption of Images Using Genetic Algorithm
No trabalho \textit{Bit-Level Encryption of Images Using Genetic Algorithm}, \citeonline{srikanth10} parte do princípio de que os padrões deixados por algoritmos de criptografia de imagens podem um dia ser facilmente quebrados, já que estes apenas mudam os \textit{pixels} de posição ou fazem embaralhamento de blocos de \textit{pixels}. O trabalho consiste em um cifrador de bloco simétrico de imagens que utiliza um conjunto \textit{N} de funções matemáticas que farão a seleção de posições dos \textit{pixels}. Assim, usando uma coordenada $(x_{1}, y_{1})$ da imagem como entrada de uma função $N_{i}$, obtêm-se uma coordenada $(x_{2}, y_{2})$, tendo-se assim, um operador de mutação.

O tipo de cruzamento utilizado é o de um ponto, sendo aplicado sobre os bits correspondentes aos \textit{pixels} selecionados. A mutação é implementada alterando-se periodicamente as funções utilizadas para a seleção. \citeonline{srikanth10} justifica que não há necessidade de selecionar os melhores descendentes visto que o algoritmo é usado especificamente para a seleção dos bits que deverão ser alterados.

O conjunto de funções e os \textit{pixels} escolhidos para serem utilizados no processo de cifragem servem como a chave secreta para o processo de decifragem. A chave, por sua vez, é cifrada utilizando o algoritmo RSA. A força do algoritmo está em não apenas trocar as posições dos \textit{pixels}, mas também alterar os seus valores por meio dos operadores do AG. Entretanto, ele depende do algoritmo RSA para fornecer segurança de fato à chave secreta, o que aumenta a complexidade na gerência da chave do algoritmo proposto e do par de chaves do RSA.

% Conclusão dos trabalhos correlatos
Pelo exposto, os principais pontos em comum vistos nos trabalhos são: o uso de blocos de texto aberto como os indivíduos do AG, ausência de função \textit{fitness} e de critério de seleção. Assim, os algoritmos propostos não efetuam, de fato, uma busca ou otimização da cifra mais segura -- o que os caracterizaria como algoritmos genéticos. Além disso, os modos de operação -- com exceção do ICIGA -- consistem basicamente nas operações de permutação e transposição, obtidos pelo cruzamento e mutação respectivamente.

% ----------------------------------------------------------
% Desenvolvimento
% ----------------------------------------------------------
\chapter[Desenvolvimento]{Desenvolvimento}


\section{Apresentação do Algoritmo Genético}

O cifrador de bloco simétrico desenvolvido utiliza os operadores clássicos de um algoritmo genético podendo ser aplicado a qualquer formato de arquivo. A chave criptográfica é gerada aleatoriamente durante o processo de cifragem. Além disso, utiliza-se o modo de operação CBC para evitar a transferência de padrões do texto aberto para a cifra.

Foi considerada utilização dos operadores do AG visto que eles são capazes de fornecer as permutações nos bytes da mensagem e aleatoriedade para aumentar a segurança da chave e da cifra. Combinado a eles, são utilizadas várias operações baseadas no OU-exclusivo (XOR) com o intuito de mascarar os valores do texto aberto. Visto ser inviável realizar a cifragem no conjunto total de bits de um arquivo, pois é possível que este possua vários \textit{megabytes} de tamanho, ela é aplicada em blocos de 64 bits. Consequentemente, o cifrador leva o \textit{padding} em consideração. A aleatoriedade da chave permite eliminar padrões que possam ser fornecidos pelo usuário. Assim, a cada execução do cifrador se obtém uma cifra e uma chave diferentes ainda que o mesmo texto aberto seja fornecido.
 
Para criar a população inicial, utilizou-se o algoritmo apresentado por \citeonline{agarwal12}, o qual recebeu o nome de \textit{derivação}. Visto que o cifrador atua indistintamente nos bits do arquivo, a cifra será equivalente a uma versão corrompida do mesmo. Isso difere, por exemplo, do cifrador desenvolvido por \citeonline{srikanth10}, que atua sobre os bits específicos dos \textit{pixels} de uma imagem, desconsiderando aqueles referentes aos cabeçalhos, campos de controle e paleta de cores, típicos na maioria dos formatos de imagem, permitindo, assim, o vazamento de informações sobre o texto aberto, como saber que se trata de uma imagem, bem como suas características de tamanho, cor, e metadados. Estes últimos, consistem em informações sobre o autor da imagem, máquina fotográfica, \textit{software} usado para edição, palavras-chaves, dentre outras.

Devido a natureza deste algoritmo genético, é necessário que todas as operações aplicadas em um indivíduo sejam reversíveis. Nesse contexto, as alterações feitas por um operador genético $O(I)$ sobre um indivíduo $I$ devem ser revertidas por um operador $R(I)$, tal como mostrado na \autoref{eq:reversivel}. No cifrador proposto, todos os operadores que realizam alterações na sequência de bits do indivíduo -- derivação, cruzamento e mutação -- são os seus próprios operadores reversíveis.

%Definição formal de operadores reversíveis
\begin{equation}
     R(O(I)) = I
     \label{eq:reversivel}
\end{equation}

Cada indivíduo do algoritmo genético é formado pela sequência de bits derivada do texto aberto, pelo valor do \textit{fitness}, e pelas subchaves, como apresentado na \autoref{fig:estrutura_individuo}. Cada subchave consiste nos parâmetros utilizados pelos operadores que foram aplicados no indivíduo em uma dada geração $G_{i}$, de modo que ao se aplicar essa subchave, obter-se-á o indivíduo tal como ele era no início da geração $G_{i}$. Ao fim das $G$ gerações do algoritmo genético, haverá $G$ subchaves para cada indivíduo. O conjunto dessas $G$ subchaves formam a chave de decifragem do algoritmo.

O processo de decifragem é realizado aplicando-se cada subchave na ordem inversa de criação, ou seja, começando pela subchave da geração $G$ e terminando com a chave da primeira geração. Esse procedimento iterativo pode ser definido formalmente pela \autoref{eq:decifragem}. Após isso, é feito o processo de derivação reversa e o cálculo do \textit{padding}, resultando, por fim, na mensagem original.

%Definição formal da decifragem
\begin{equation}
     D_{kg}(I_{g}) = I_{g-1} ~~ \forall ~g \in \{ G, G-1, G-2, \dots , 0 \}
     \label{eq:decifragem}
\end{equation}
\noindent onde $D(I)$ é a aplicação de uma subchave em um indivíduo $I$ de uma dada geração $g$, e $G$, o total de gerações do algoritmo genético.

% Diagrama dos componentes de um indivíduo
\begin{figure}
  \centering
    \includegraphics[scale=0.4]{Imagens/estrutura_individuo}
\caption{Componentes de um indivíduo do AG.}
\label{fig:estrutura_individuo}
\end{figure}

De forma geral, os passos para a cifragem são como se seguem. O texto aberto fornecido é divido em blocos de 64 bits e cada um passa pelo processo de derivação, o qual realiza pequenas alterações nos valores dos bytes de cada bloco, com o intuito de simular a geração de indivíduos aleatórios. O \textit{fitness} é calculado e o novo indivíduo é armazenado. As derivações são realizadas até que se obtenha o número desejado de indivíduos da população. Após isso, é realizada uma seleção por torneio e os indivíduos selecionados passarão pelo cruzamento e mutação, e em seguida é recalculado o valor do \textit{fitness} de cada um. Tais indivíduos substituirão aqueles que possuem os menores valores de \textit{fitness} na população, resultando em um novo conjunto de indivíduos para a próxima geração. Essas operações são executadas até se atingir o número máximo de gerações do algoritmo genético. Nesse ponto, o melhor indivíduo -- maior \textit{fitness} -- é selecionado como a cifra do texto aberto, se extraindo a sua sequência binária e todas as suas subchaves. A \autoref{fig:diagrama_atividades} apresenta o diagrama de atividades referente ao algoritmo desenvolvido.


\begin{figure}
 \centering
   \includegraphics[scale=0.30]{Imagens/Diagrama_de_Atividades}
   \caption{Diagrama de Atividades do Algoritmo Genético Proposto.}
   \label{fig:diagrama_atividades}
\end{figure}

%Diagrama de Atividades do AG
% \begin{landscape}

% 	\begin{figure}[p]
		  
% 	        \includegraphics[width=\linewidth,height=\textheight,keepaspectratio]{Imagens/Diagrama_de_Atividades}
	    
% 	    \caption{Diagrama de Atividades do Algoritmo Genético Proposto.}
% 	    \label{fig:diagrama_atividades}
% 	\end{figure}
% \end{landscape}

%TODO encaixar isso em algum lugar.
%\section{Abordagens Utilizadas}
%Falar de algoritmos que usam cada bloco como indivíduo, o plaintext como indivíduo (limitações, maximiza a troca de informações), aqueles que não consideram padding, função hash


\section{Operadores}

\subsection{Derivação}

A derivação constitui o processo de inicialização do algoritmo genético. Seu objetivo é formar a população inicial por meio de alterações rândomicas em blocos do texto aberto, de forma a simular a geração de indivíduos aleatórios. O algoritmo utilizado é o mesmo proposto por \citeonline{agarwal12} e seu pseudo-código é mostrado no algoritmo \autoref{alg:derivacao}. Assim, o texto aberto pode ser visto como o indivíduo inicial do algoritmo, que será derivado de acordo com os parâmetros $D_{a}, D_{b}, D_{k} \in [0, 7]$. Dado um bloco $X$, com 8 bytes, identificados de 0 a 7, $D_{a}$ e $D_{b}$ especificam as posições a serem trocadas, enquanto que $D_{k}$ indica a posição a ter o seu respectivo valor substituído pelo seu complementar de 255.

O diagrama da \autoref{fig:operador_derivacao} apresenta como os bytes de cada bloco são alterados. Nota-se que, como as modificações utilizam informações do mesmo bloco, se pode considerar o derivação como um processo de mutação.

%Algortmo de derivação
\begin{algorithm}
%     \SetLine
     \Entrada{Array $X$ de tamanho $TAM$ com blocos de 8 bytes}
     \Saida{Array $X$ de tamanho $TAM$ com blocos de 8 bytes}
     \BlankLine
     
     $Da \leftarrow NumeroAleatórioEntre(0,7)$\;
     $Db \leftarrow NúmeroAleatórioEntre(0,7)$\;
     $Dk \leftarrow NúmeroAleatórioEntre(0,7)$\;
     \Para{$i \leftarrow 0$ \Ate $TAM$} {
          $bloco \leftarrow X[i]$\;
          $temp \leftarrow bloco[ Da ]$\;
          $bloco[ Da ] \leftarrow bloco[ Db ]$\;
          $bloco[ Db ] \leftarrow temp$\;
          $bloco[ Dk ] \leftarrow 255 - bloco[ Dk ]$\;
     }
     
     \caption{Derivação}
     \label{alg:derivacao}
\end{algorithm}

% Diagrama da derivação
\begin{figure}[b]
  \centering
    \includegraphics[scale=0.4]{Imagens/operador_derivacao}
\caption{Processo de derivação aplicado em um bloco.}
\label{fig:operador_derivacao}
\end{figure}


\subsection{Seleção por Torneio}

O algoritmo genético utiliza a seleção por torneio binária, retornando uma quantidade específica de indivíduos, de acordo com o tamanho da população usada. Em um torneio binário, sempre dois indivíduos irão disputar uma rodada, o que permite com que o algoritmo selecione os melhores indivíduos frequentemente. Aumentando a quantidade de indivíduos que participarão em cada rodada, os melhores indivíduos serão selecionados ainda mais frequentemente, o que tende a diminuir a diversidade de informações no AG o que, consequentemente, tornaria o cifrador vulnerável a ataques de criptoanálise, dada a previsibilidade nesse operador. A descrição de como a seleção é realizada é dada a seguir.

Primeiramente, se calcula quantos indivíduos serão selecionados, que pode ser por exemplo, 40\% do total de indivíduos da população. Se o valor de individuos selecionados for 5, o torneiro terá 5 rodadas. Em cada rodada, são selecionados aleatoriamente dois indivíduos da população. O indivíduo que possuir maior \textit{fitness} é selecionado e outra rodada começa. Ao fim das rodadas se tem o conjunto de indivíduos que participarão do cruzamento e da mutação.

\subsection{Função \textit{Fitness}}

Em criptografia, todos os cifradores devem injetar entropia no texto aberto para que a cifra não contenha qualquer padrão ou estrutura característica que possa ser associada. Nesse sentido, os operadores são os responsáveis pelo aumento do valor de entropia bem como o ocultamento dos padrões do texto aberto. Portanto, a função \textit{fitness} consiste na maximização do valor da entropia presente na sequência binária de cada indivíduo, a qual é calculada pela \autoref{eq:entropia_cifrador}, normalizada no intervalo $[0,1]$.

\begin{equation} \label{eq:entropia_cifrador}
H(X) = - \displaystyle\sum_{x}^{} P(x) log _{256} [P(x)]
\end{equation}

É utilizado $log_{256}$ para que o valor da entropia seja expresso em bytes, visto que estes possuem 256 valores possíveis -- $2^{8}$ bits. Similarmente, se pode usar outros valores para a base do logaritmo dependendo da unidade desejada. Por exemplo, $log_{2}$ fornece o resultado em binário e $log_{10}$ em decimal.

Vale ressaltar, que a entrada do cifrador pode ser um texto aberto que já possua um alto valor de entropia, de forma que o cifrador deverá realizar tão somente a retirada de qualquer padrão por meio dos operadores do algoritmo genético.

\subsection{Cruzamento}

%não adianta fazer um crossover unitário se não haverá troca de informações entre os indivíduos e portanto não teremos um algoritmo genético.
O operador de cruzamento tradicional recebe como entrada dois indivíduos nos quais realiza a troca de informações. No entanto, aplicar esse raciocínio em um cifrador de bloco se mostra inviável, dado que cada indivíduo terá o mesmo tamanho do texto aberto, resultando em uma demanda por memória e processamento elevado, proporcional ao tamanho da população. Além disso, verificou-se que o aumento da entropia é maior quando o cruzamento é aplicado em blocos, como apresenta a \autoref{tab:com_cruzamento}, resultado de um teste com os valores médios de 10 execuções de cada abordagem. A diferença se deve a tendência que o cruzamento de um ponto aplicado em indivíduos tem de substituir apenas as partes finais do cromossomo do indivíduo, de forma a não impactar muito na configuração original presente nas partes iniciais do cromossomo. Nesse contexto, o cifrador desenvolvido utiliza o cruzamento sobre dois blocos consecutivos da sequência binária de um indivíduo. O ponto de cruzamento, denominado $C_{p}$, é escolhido aleatoriamente no intervalo $[0,7]$ e seu valor representa um dos 8 bytes presentes no bloco.

\begin{table}[h]
\centering
\setlength{\tabcolsep}{30pt}
\renewcommand{\arraystretch}{1.3}
\begin{tabular}{r|c|c|}
\cline{2-3}
\multicolumn{1}{l|}{}                               & \textbf{Blocos} & \textbf{Indivíduos} \\ \hline
\multicolumn{1}{|r|}{\textbf{Entropia média final}} & 0,9990195456    & 0,9437447842        \\ \hline
\multicolumn{1}{|r|}{\textbf{Desvio-padrão}}        & 0,0001156682    & 0,0045605187        \\ \hline
\end{tabular}
\caption{Comparação entre o cruzamento aplicado entre indivíduos e entre blocos no aumento da entropia.}
\label{tab:com_cruzamento}
\end{table}

Esse operador trabalha utilizando o modo de operação CBC apresentado na \autoref{fig:cbc_mode} da página \pageref{fig:cbc_mode}. Logo, é necessário um vetor de inicialização, denominado $C_{iv}$, que consiste em um \textit{array} com o dobro do tamanho de um bloco -- 128 bits -- sendo gerado de forma aleatória.

Dados dois blocos consecutivos \texttt{X} e \texttt{Y}, executa-se a operação XOR entre cada valor do bloco com o vetor de inicialização $C_{iv}$, motivo pelo qual ele possui duas vezes o tamanho do bloco. Em seguida, o cruzamento em si é realizado trocando-se, a partir do ponto de cruzamento, os valores do bloco \texttt{X} com os valores iniciais do bloco \texttt{Y} até se atingir uma posição anterior ao ponto de cruzamento no bloco \texttt{Y}, tal como exemplificado na \autoref{fig:cruzamento}. Essa maneira de trocar os dados entre os blocos permite que a concatenação dos blocos resultantes possua uma permutação mais complexa do que se fosse utilizado o cruzamento de um ponto tradicional. Note-se que as trocas realizadas fornecem uma permutação, e a operação XOR, transposição. O algoritmo \autoref{alg:cruzamento} apresenta como o cruzamento pode ser efetuado.

% Diagrama do crossover
\begin{figure}
  \centering
    \includegraphics[scale=0.35]{Imagens/crossover_unitario}
\caption{Cruzamento aplicado nos blocos \texttt{X} e \texttt{Y}, com ponto de cruzamento indicado pela seta, e a concatenação dos blocos resultantes \texttt{X'} e \texttt{Y'}.}
\label{fig:cruzamento}
\end{figure}

%Algoritmo de cruzamento
\begin{algorithm}
%     \SetLine
     \Entrada{Dois blocos A e B de tamanho TAM}
     \Saida{Dois blocos A e B de tamanho TAM}
     \BlankLine
     
     Cp $\leftarrow$ Número aleatório entre 0 e 7\;
     Cvi[0 .. 2 * TAM] $\leftarrow$ valores aleatorios\;
     
     \Para{$i \leftarrow 0$ \Ate $TAM$} {
     	A[i] $\leftarrow$ A[i] XOR Cvi[i]\;
     }
     
     \Para{$i \leftarrow 0$ \Ate $TAM$} {
     	B[i] $\leftarrow$ B[i] XOR Cvi[i + 8]\;
     }
     
     \Para{$i \leftarrow 0$ \Ate $Cp$} {
     	temp $\leftarrow$ B[i] XOR Cvi[i]\;
     	pos $\leftarrow$ (i + Cp) \% 8\;
     	B[i] $\leftarrow$ A[pos]\;
     	A[pos] $\leftarrow$ temp\;
     }
     
     \tcp{Na próxima execução, as cifras geradas serão usadas no lugar do vetor de inicialização.}
     Cvi[0..7] $\leftarrow$ A\;
     Cvi[8..16] $\leftarrow$ B\;
    
     
     \caption{Cruzamento}
     \label{alg:cruzamento}
\end{algorithm}


\subsection{Mutação}

A mutação consiste em um rearranjo dos bytes bem como a modificação de seus valores. Os parâmetros, escolhidos aleatoriamente, são o ponto de mutação, denominado $M_{p} \in [0, 7]$, e o valor de mutação, denominado $M_{v} \in [0, 255]$. A partir do ponto de mutação os valores são deslocados para o início e os valores anteriores a ele são deslocados para o fim, como apresenta a \autoref{fig:mutacao}. Antes da troca porém, é feita a operação XOR entre o valor do gene atual com $M_{v}$, de forma a fornecer, também, a característica de transposição do texto aberto. O pseudo-código é apresentado no algoritmo \autoref{alg:mutacao}.

% Diagrama da mutação
\begin{figure}
  \centering
    \includegraphics[scale=0.35]{Imagens/mutacao}
\caption{Mutação aplicada no bloco \texttt{A} na posição 3 resultando no bloco \texttt{A'}.}
\label{fig:mutacao}
\end{figure}

Percebe-se que pela mutação proposta todos os genes são alterados, diferentemente dos operadores de mutação tradicionais, onde apenas alguns sofrem mudança. Entretanto, se faz necessário aumentar a complexidade e imprevisibilidade do operador para tornar o cifrador resistente a ataques de criptoanálise. Além disso, dado que a operação de mutação contribui para o aumento da entropia e que apenas 40\% dos indivíduos da população passarão por ele em uma dada geração, afixou-se a taxa de mutação em 100\% a fim de que todos os indivíduos selecionados tenham oportunidade de aumentar o valor da entropia.

%Algoritmo da mutação
\begin{algorithm}
     \Entrada{Um bloco A de tamanho TAM}
     \Saida{Um bloco A de tamanho TAM}
     \BlankLine
     
     Mp $\leftarrow$ Número aleatório entre 0 e 7 inclusive\;
     Mv $\leftarrow$ Número aleatório entre 0 e 255 inclusive\;
          
     \Para{$i \leftarrow 0$ \Ate $TAM$} {
     	blocoCifrado[i] $\leftarrow$ A[(Mp + i) \% TAM ] XOR Mv\;
     }
          
     \caption{Mutação}
     \label{alg:mutacao}
\end{algorithm}


\subsection{Seleção dos Sobreviventes}

Para a seleção dos sobreviventes a população é ordenada em forma crescente de acordo com o valor do \textit{fitness} de cada indivíduo. Em seguida, os indivíduos resultantes do cruzamento e da mutação substituem aqueles com menor \textit{fitness} na população. Pode-se perceber que a população possui um tamanho constante, necessário para não gerar uma sobrecarga elevada na execução do cifrador caso se desejasse aramazenar todos os indivíduos gerados.


\section{Chave}
%gráfico comparando o número de gerações com o tamanho da chave.
A chave de decriptografia é composta por todas as subchaves do melhor indivíduo selecionado, ao fim das gerações do AG, para ser a cifra do texto aberto. Os parâmetros presentes em cada subchave são detalhados na \autoref{tab:parametros}. Note-se que o tamanho da chave final é dependente da quantidade de gerações que o AG possui. Assim, os parâmetros referentes aos operadores de cruzamento e mutação aumentam conforme o número de gerações enquanto que o valor do \textit{padding} e da operação de derivação são fixos, permitindo que o tamanho da chave seja calculado conforme a \autoref{eq:tamanho_chave}.

\begin{equation}
S_{k} = 32 + 40 G ~bits, ~\forall ~G > 0 \in \mathbb{N}
\label{eq:tamanho_chave}
\end{equation}
\noindent onde $S_{k}$ é o tamanho da chave e $G$ a quantidade de gerações do AG.


\begin{table}
\centering
\setlength{\tabcolsep}{30pt}
\renewcommand{\arraystretch}{1.3}
\begin{tabular}{|c|c|}
\hline
\textbf{Parâmetros} & \textbf{Tamanho em bits} \\ \hline
\textit{Padding}    & 8                        \\ \hline
\multicolumn{2}{|c|}{\textbf{Derivação}}       \\ \hline
$D_{a}$                  & 8                        \\ \hline
$D_{b}$                  & 8                        \\ \hline
$D_{k}$                  & 8                        \\ \hline
\multicolumn{2}{|c|}{\textbf{Cruzamento}}      \\ \hline
$C_{p}$                  & 8                        \\ \hline
$C_{iv}$                 & 16                       \\ \hline
\multicolumn{2}{|c|}{\textbf{Mutação}}         \\ \hline
$M_{p}$                  & 8                        \\ \hline
$M_{v}$                  & 8                        \\ \hline
\end{tabular}

\caption{Especificação dos tamanhos de cada parâmetro de uma subchave.}
\label{tab:parametros}
\end{table}




% ----------------------------------------------------------
% Resultados
% ----------------------------------------------------------
\chapter[Resultados Experimentais]{Resultados Experimentais}

\section{Testes Realizados}

Foram realizados testes com o objetivo de se definir qual a quantidade de gerações mais adequada -- que aumente consideravelmente o valor da entropia -- e qual os limites de tempo de execução e tamanho do texto aberto na geração constada, além de verificar se a cifra não se assemelha visualmente ao seu respectivo texto aberto. Foram utilizados tipos comuns de arquivo -- texto, imagem e áudio -- a fim de verificar a não-existência de qualquer padrão óbvio visível na cifra. A implementação do cifrador foi feita na linguagem de programação Java e as características do ambiente de testes utilizado estão detalhados na \autoref{tab:ambiente_teste}.

\begin{table}[h]
\setlength{\tabcolsep}{30pt}
\renewcommand{\arraystretch}{1.3}
\centering
\begin{tabular}{|l|l|}
\hline
\textbf{Sistema Operacional} & Ubuntu 12.04 LTS                         \\ \hline
\textbf{Tipo de Sistema}     & 32 bits                                  \\ \hline
\textbf{Memória RAM}         & 2 Gb                                     \\ \hline
\textbf{Processador}         & Intel Pentium CPU B950 2.10GHz $\times$ 2 \\ \hline
\end{tabular}
\caption{Especificações do ambiente de testes.}
\label{tab:ambiente_teste}
\end{table}


\subsection{Quantidade de Gerações}

Este teste consiste em avaliar o aumento do valor da entropia de acordo com a quantidade de gerações no AG. Para tanto, foi criado um arquivo texto chamado \texttt{ag\_original.txt} que consistia na frase \textquotedblleft \texttt{The quick brown fox jumps over the lazy dog}\textquotedblright ~repetida mil vezes, resultando em um arquivo de 45.000 bytes com valor de entropia igual a 0.635663616. Dado o fato da frase ser repetida por todo o arquivo, o valor da entropia é relativamente pequeno visto que não há muita imprevisibilidade nos dados. Assim, com um texto aberto com pouca entropia, pode-se analizar o quanto de entropia é inserido pelo algoritmo genético, de acordo com a quantidade de gerações.

Para cada geração analisada, foram realizadas 10 execuções, e os valores médios foram plotados no gráfico da \autoref{fig:teste_geracao}. Percebe-se como o algoritmo genético aumenta a entropia aumentando a quantidade de gerações, chegando próximo do valor teórico máximo 1. Vale notar que a partir de 50 gerações o AG não consegue inserir mais entropia, resultando apenas em mais aumento de processamento do que no valor da entropia. Por esse motivo, afixou-se em 50 a quantidade de gerações do algoritmo genético gerando, portanto, uma chave de 2032 bits, conforme a \autoref{eq:tamanho_chave} da página \pageref{eq:tamanho_chave}.

%Gráfico da entropia por geração.
\begin{figure}
     \begin{center}
          \includegraphics{Imagens/teste_geracao}
          \caption{Aumento da entropia de um texto aberto com valor inicial igual a 0,63.}
          \label{fig:teste_geracao}
     \end{center}
\end{figure}


\subsection{Arquivo de Texto}

Um dos arquivos mais simples e comumente submetido à criptografia é do tipo texto. Foi utilizado o mesmo arquivo \texttt{ag\_original.txt} apresentado na seção anterior visto que ele gera uma situação bem desfavorável quanto a entropia e pode ser considerado uma situação de pior caso. Dessa forma, comparou-se os arquivos de texto aberto e a cifra quanto ao tamanho, entropia e valor de \textit{hash}, como apresentado na \autoref{tab:teste_texto}.

Pelos dados da tabela, houve um aumento de cerca de 57,2\% na entropia do arquivo, bem como não foi constatado nenhum padrão aparente na cifra, como pode ser observado na subfigura \ref{fig:texto_ciphertext}. Na cifra apresentada na \autoref{fig:texto_sem_cbc}, é possível observar que, embora os caracteres sejam ilegíveis, ainda existem padrões entre eles, o que potencialmente pode ser utilizado para recuperar informações sobre o texto aberto por ataques de criptoanálise, mostrando, portanto, a importância do uso do modo de operação CBC.

O \textit{software} utilizado para a visualização do texto foi o \citeauthoronline{gedit}, o qual tenta converter os bytes da cifra que não representam algum caractere de texto válido resultando em vários trechos semelhantes a \texttt{$\backslash$D2}, \texttt{$\backslash$F5}, etc.

%Comparação entre os arquivos de texto aberto e cifrado.
\begin{table}[h]
\renewcommand{\arraystretch}{1.3}
\centering
\begin{tabular}{r|l|l|}
\cline{2-3}
\multicolumn{1}{l}{}                    & \multicolumn{1}{|c|}{\textbf{Texto aberto}} & \multicolumn{1}{|c|}{\textbf{Cifra}} \\ \hline
\multicolumn{1}{|r|}{\textbf{Nome}}     & ag\_original.txt                            & ag\_cripto.txt                       \\ \hline
\multicolumn{1}{|r|}{\textbf{Tamanho}}  & 45000 bytes                                      & 45000 bytes                               \\ \hline
\multicolumn{1}{|r|}{\textbf{Entropia}} & 0,635663616                                 & 0,9991175372713945                   \\ \hline
\multicolumn{1}{|r|}{\textbf{MD5}}      & 7dc907c6b5e106d368d80e235774d09b            & 6b43a86a284e840f3f550c64112a4c3b     \\ \hline
\end{tabular}

\caption{Comparação entre os arquivos de texto aberto e cifrado.}
\label{tab:teste_texto}
\end{table}

%Comparação visual entre o texto aberto e a cifra.
\begin{figure}
  \centering
  \subbottom[Trecho inicial do texto original.]{%
    \includegraphics[width=0.4\linewidth]{Imagens/teste_texto_original}
    \label{fig:texto_plaintext}
    }
  \subbottom[Trecho inicial do texto cifrado.]{%
    \includegraphics[width=0.5\linewidth]{Imagens/teste_texto_cifra}
    \label{fig:texto_ciphertext}
    }
  \caption{Comparação visual entre o texto aberto e a cifra.}
  \label{fig:teste_texto}
\end{figure}

\begin{figure}
     \begin{center}
          \includegraphics[scale=0.7]{Imagens/teste_texto_sem_cbc}
          \caption{Cifra resultante sem a utilização do modo CBC e alguns padrões destacados.}
          \label{fig:texto_sem_cbc}
     \end{center}
\end{figure}


\subsection{Arquivo de Imagem}

Visto que o cifrador criptografa todos os bytes do texto aberto, sem levar em consideração qualquer estrutura que ele possa ter, criptografar uma imagem equivale a gerar uma cifra que não pode ser exibida em programas de visualização de imagens tal como foi feito com texto. Entretando, para fornecer uma representação visual da cifra, este teste procedeu da seguinte forma: removeu-se os bytes referentes aos cabeçalhos e outras estruturas de controle da imagem, cifrou-se os bytes referentes aos \textit{pixels} e os reinseriu junto ao cabeçalho -- de modo que visualizadores de imagens comuns pudessem reconhecer a cifra.

A imagem utilizada -- \texttt{lena.jpg} -- é uma imagem do tipo JPEG com 512 de altura e 512 de largura e 37.788 bytes de tamanho. A \autoref{tab:teste_imagem} apresenta os detalhes dos arquivos de texto aberto e da cifra e a \autoref{fig:teste_lena} apresenta um comparativo entre eles. Como pode-se perceber, a imagem cifrada, mostrada na subfigura \ref{fig:lena_ciphertext}, apresenta os pixels arranjados de forma pseudo-aleatória, de modo que os pixels estão distribuídos uniformemente, ocultando visualmente qualquer semelhança com a imagem original. A distribuição uniforme dos pixels e a grande variedade dos seus valores são consequência da alta entropia inserida.

%Comparação entre o texto aberto e a cifra de lena.jpg
\begin{table}[b]
\renewcommand{\arraystretch}{1.3}
\centering
\begin{tabular}{r|l|l|}
\cline{2-3}
\multicolumn{1}{l}{}                           & \multicolumn{1}{|c|}{\textbf{Texto aberto}} & \multicolumn{1}{|c|}{\textbf{Cifra}} \\ \hline
\multicolumn{1}{|r|}{\textbf{Nome}}            & lena.jpg                                    & ag\_cripto.jpg                       \\ \hline
\multicolumn{1}{|r|}{\textbf{Tamanho}} & 786.432 bytes                                    & 786.432 bytes                             \\ \hline
\multicolumn{1}{|r|}{\textbf{Entropia}}        & 0,9740204484101845                          & 0,9999763766628336                   \\ \hline
\multicolumn{1}{|r|}{\textbf{MD5}}             & 5dc312277a0ead907d3b133cfd854819            & 0fe739cf8823c675e027b504ef28d289     \\ \hline
\end{tabular}
\caption{Comparação entre o texto aberto e a cifra de \texttt{lena.jpg}.}
\label{tab:teste_imagem}
\end{table}

%Comparação visual entre o texto aberto e a cifra de lena.jpg
\begin{figure}[h]
  \centering
  \subbottom[Imagem original.]{
    \includegraphics[width=0.3\linewidth]{Imagens/lena_plaintext}
    \label{fig:lena_plaintext}
    }
  \subbottom[Imagem cifrada.]{
    \includegraphics[width=0.3\linewidth]{Imagens/lena_ciphertext}
    \label{fig:lena_ciphertext}
    }
  \caption{Comparação visual entre o texto aberto e a cifra de \texttt{lena.jpg}.}
  \label{fig:teste_lena}
\end{figure}


\subsection{Arquivo de Áudio}

Similarmente ao que foi exposto na criptografia de imagens, os cabeçalhos e estruturas de controle presentes em arquivos de áudio também não são considerados durante a cifragem. Dessa forma, este teste funciona de maneira análoga ao teste de imagem. O arquivo utilizado é \texttt{sample.wav} -- 171.070 bytes, que é do tipo WAVE com as seguintes especificações de áudio:

\begin{itemize}
     \item 1 segundo de duração
     \item 1 canal (Mono)
     \item Taxa de amostragem em 44100 Hz (32 bits)
     \item Little-endian
     \item Signed 16 bit PCM como codificação
\end{itemize}

A \autoref{tab:teste_audio} apresenta os detalhes do texto aberto e da cifra referente ao arquivo \texttt{sample.wav}. O aumento de 2 bytes no tamanho da cifra é consequência do \textit{padding}.

%Comparação dos arquivos de áudio.
\begin{table}[h]
\renewcommand{\arraystretch}{1.3}
\centering
\begin{tabular}{r|l|l|}
\cline{2-3}
\multicolumn{1}{l}{}                    & \multicolumn{1}{|c|}{\textbf{Texto aberto}} & \multicolumn{1}{|c|}{\textbf{Cifra}} \\ \hline
\multicolumn{1}{|r|}{\textbf{Nome}}     & sample.wav                                  & ag\_cripto.wav                       \\ \hline
\multicolumn{1}{|r|}{\textbf{Tamanho}}  & 171.070 bytes                               & 171.072 bytes                        \\ \hline
\multicolumn{1}{|r|}{\textbf{Entropia}} & 0,8972636790368798                          & 0,9998875980710717                   \\ \hline
\multicolumn{1}{|r|}{\textbf{MD5}}      & dc5a4be80823e1e11148ecb5ef534ab8            & dc5a6012a48d9eeeb4a40dcc85b41140     \\ \hline
\end{tabular}

\caption{Comparação entre o áudio original e a cifra de \texttt{sample.wav}.}
\label{tab:teste_audio}
\end{table}

A \autoref{fig:teste_audio} mostra as formas de onda, ou \textit{waveforms}, do áudio original e da cifra. Como pode-se perceber, o texto aberto possui uma onda característica enquanto que a cifra possui uma representação mais homogênea e de maior amplitude -- consequência da variedade dos valores dos bytes -- resultando em ruído ao ser reproduzido e, portanto, sem qualquer característica audível que relacione a cifra com o áudio original. Essas características são consequências da alta entropia presente na cifra. O \textit{software} utilizado na elaboração das formas de onda foi o \citeauthoronline{audacity}.

%Comparação visual entre o texto aberto e a cifra de sample.wav
\begin{figure}[h]
  \centering
  \subbottom[\textit{Waveform} do áudio original.]{
    \includegraphics[width=0.45\linewidth]{Imagens/teste_audio_plain}
    \label{fig:wav_plaintext}
    }
  \subbottom[\textit{Waveform} do áudio cifrado.]{
    \includegraphics[width=0.45\linewidth]{Imagens/teste_audio_cipher}
    \label{fig:wav_ciphertext}
    }
  \caption{Comparação visual entre o texto aberto e a cifra de \texttt{sample.wav}.}
  \label{fig:teste_audio}
\end{figure}


\section{Discução Sobre os Resultados}

Pelo exposto, as condições adequadas de execução do cifrador estão descritas na \autoref{tab:resumo_operadores}. Já o gráfico da \autoref{fig:tam_chave} mostra como o tamanho da chave aumenta se forem utilizadas muitas gerações, o que aumenta o processamento do algoritmo e a gerência de chaves desnecessariamente grandes. Assim, admintindo um crifrador perfeito com uma chave de 256 bits, um ataque de força bruta teria que analizar pelo menos metade de todas as $2^{256}$ chaves possíveis. Logo, é necessário encontrar um ponto de equilíbrio entre o nível de segurança e a usabilidade do cifrador -- desempenho.

\begin{table}[h]
\renewcommand{\arraystretch}{1.3}
\centering
\begin{tabular}{|r|l|}
\hline
\multicolumn{2}{|c|}{\textbf{Parâmetros}}          \\ \hline
Quantidade de gerações                & 50         \\ \hline
Quantidade de indivíduos              & 10         \\ \hline
Função Fitness                        & Entropia   \\ \hline
Proporção  de indivíduos selecionados & 40\%       \\ \hline
Tamanho da seleção por torneio        & 2          \\ \hline
Taxa de mutação                       & 100\%      \\ \hline
Tamanho da chave                      & 2.032 bits \\ \hline
\end{tabular}
\caption{Resumo dos parâmetros do algoritmo genético.}
\label{tab:resumo_operadores}
\end{table}

% Gráfico da chave
\begin{figure}
  \centering
    \includegraphics[scale=0.7]{Imagens/chave}
\caption{Tamanho da chave de acordo com a quantidade de gerações.}
\label{fig:tam_chave}
\end{figure}

%TODO
%\section{Desempenho do Algoritmo}


% ----------------------------------------------------------
% Conclusão
% ----------------------------------------------------------
\chapter[Conclusões]{Conclusões}

\section{Contribuições}

O cifrador simétrico baseado em algoritmo genético mostrou-se eficiente no que diz respeito a inserção de entropia no arquivo de texto aberto assim como na chave, visto que ela é gerada durante a cifragem de forma aleatória. O cifrador proposto inclui em seu funcionamento a maioria dos operadores clássicos de um algoritmo genético -- seleção, cruzamento, mutação -- e outros conceitos como população e indivíduos. Constatou-se que em diferentes tipos de arquivo, a cifra gerada pelo algoritmo genético não possui qualquer padrão visível que a relacione com a mensagem original, resultado da entropia. Além disso, verificou-se que a implementação do modo de operação \textit{Cipher-block Chaining} (CBC) se mostra crucial para o aumento de entropia e evita que padrões do texto aberto sejam refletidas na cifra. Dessa forma, o trabalho fornecerá mais uma alternativa de proteção de dados, o que pode economizar recursos computacionais caso se deseje criptografar dados não tão sensíveis utilizando métodos bastante sofisticados

A maior limitação constatada está no tamanho da chave que, apesar de ser ajustável de acordo com a quantidade de gerações utilizadas, requer em torno de 50 gerações para fornecer um nível de entropia próximo do valor máximo de 1, isto é, para se conseguir um nível mínimo de segurança na cifra são precisas 50 gerações. Além disso, verifica-se que o custo computacional para cifragem não aumenta linearmente com o aumento do tamanho da mensagem a ser cifrada, fazendo com que o algoritmo proposto seja mais adequado a mensagens de tamanho reduzido.

\section{Trabalhos Futuros}
%TODO
% Como trabalhos futuros, recomenda-se a análise do 
%  o desenvolvimento de ataques criptoanalíticos contra o cifrador a fim de se detectar falhas no \textit{design} e propor novas melhorias.
Os conhecimentos resultantes deste trabalho configuram uma abordagem que pode ser utilizada para criptografia bem como para algoritmos genéticos. Faz-se necessário, portanto, aplicar os operadores propostos em cifradores de bloco que não utilizem a aborgadem de algoritmos genéticos no seu modo de operação, de forma a se verificar o impacto que é produzido por eles na geração de entropia.
Recomenda-se, também, um estudo para o aprimoramento dos operadores utilizados a fim de que o tamanho da chave seja reduzido, facilitanto, assim, a gerência e troca das mesmas. Além disso, sugere-se um estudo de como o cifrador é seguro em relação a ataques criptoanalíticos mais comuns, como criptoanálise linear ou diferencial. Dessa forma, pode-se verificar se o modo de operação baseado em algoritmo genético deixa vazar informações do texto aberto para a cifra.

% ----------------------------------------------------------
% ELEMENTOS PÓS-TEXTUAIS
% ----------------------------------------------------------
\postextual


% ----------------------------------------------------------
% Referências bibliográficas
% ----------------------------------------------------------
\bibliography{referencias}


\end{document}
